package DP;

import java.util.Arrays;

/**
 * 647.回文子串
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串
 * 当s[i]与s[j]不相等，dp[i][j]一定是false。
 * 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况
 * 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
 * 情况二：下标i 与 j相差为1，例如aa，也是回文子串
 * 情况三：下标：i 与 j相差大于1的时候，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
 * dp[i][j]是由dp[i + 1][j - 1]是否为true推导出来的，所以从下到上，从左到右遍历
 * dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。
 */
public class countSubstrings {
    /**
     * 一刷
     */
    public int countSubstrings(String s) {
        //建议使用简单类型，如果使用包装类型，未初始化则会定义为null
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {  //两个for循环不可以颠倒，因为需要保证j>=i，只有先确定了i才能确定j
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        count++;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    /**
     * 二刷
     */
    class Solution {
        public int countSubstrings(String s) {
            boolean dp[][] = new boolean[s.length()][s.length()];
            int res = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = s.length() - 1; j >= 0; j--) {
                    if (i == j) {
                        res++;
                        dp[i][j] = true;
                    }
                    if (j - i == 1 && s.charAt(i) == s.charAt(j)) {
                        res++;
                        dp[i][j] = true;
                    }
                    if (j - i > 1 && dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
            return res;
        }
    }
}
